class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for(int i = 0; i < n - 2; i++)
        {
            if(i > 0 && nums[i] == nums[i - 1]) continue;   // 跳过相同的数，和下面两个while同个道理
            int x = nums[i];
            int j = i + 1;
            int k = n - 1;

            // 两个优化
            if(x + nums[i + 1] +nums[i + 2] > 0) break;
            if(x + nums[n - 1] + nums[n - 2] < 0) continue;

            vector<int> tmp;
            while(j < k)
            {
                
                int sum = x + nums[j] + nums[k];
                if(sum == 0)
                {
                    tmp.push_back(x);
                    tmp.push_back(nums[j]);
                    tmp.push_back(nums[k]);
                    ans.push_back(tmp);
                    tmp.clear();
                    
                    while(++j < n && nums[j] == nums[j - 1]);
                    while(--k > j && nums[k + 1] == nums[k]);
                }
                else if(sum > 0) k--;
                else if(sum < 0) j++;
            }
        }
        return ans;
    }
};